package JZ;

import java.util.*;

public class Title {

    public static ArrayList<String> Permutation (String str) {
        char[] s = str.toCharArray();
        LinkedList<Character> list  = new LinkedList<>();
        ArrayList<String> result = new ArrayList<>();
        boolean[] flag = new boolean[str.length()];
        dfs(s,list,result, flag);
        return result;
    }

    private static void dfs(char[] s, LinkedList<Character> list, ArrayList<String> result, boolean[] flag) {
        if(list.size()==s.length){
            StringBuilder stringBuilder = new StringBuilder();
            for (char c: list) {
                stringBuilder.append(c);
            }
            result.add(stringBuilder.toString());
            return;
        }
        /**
         * 剪枝
         */
        Set<Character> flagV = new HashSet<>();
        for (int i = 0; i < s.length; i++) {
            if(flag[i]){
                continue;
            }
            if(!flagV.add(s[i])){
                continue;
            }
            flag[i] = true;
            list.offer(s[i]);
            dfs(s,list,result,flag);
            list.removeLast();
            flag[i] = false;
        }
    }

    public static void main(String[] args) {
        Permutation("aaa");
    }
}
